package com.google.ant.extensions.types;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

import org.apache.tools.ant.BuildException;

public class Resolver {
    private Map<Module, Collection<Module>> depModulesMap = new HashMap<Module, Collection<Module>>();
    
    public void resolve2(Collection<Module> modules, Collection<Module> results, int lastResultsCount) {
        Collection<Module> toRemove = new ArrayList<Module>();

        for (Module module : modules) {
            //System.out.println("*** " + module + module.getDependencies());
            if (!depModulesMap.containsKey(module)) {
                Collection<Module> depModules = new ArrayList<Module>();
                depModules.addAll(module.getDependencies());
                depModulesMap.put(module, depModules);
            }

            Collection<Module> depModules = depModulesMap.get(module);

            if (depModules.isEmpty()) {
                toRemove.add(module);
                results.add(module);
            }

            if (depModules.size() == 1 && results.contains(depModules.iterator().next())) {
                toRemove.add(module);
                results.add(module);
            }
            if (depModules.size() > 1) {
                removeDependency(depModules, results);
            }
        }

        //System.out.println("to remove: " + toRemove);
        //System.out.println("results: " + results);

        if (lastResultsCount == results.size()) {
            checkCycleDependencies(modules);
        }

        for (Module m : toRemove) {
            modules.remove(m);
        }

        if (!modules.isEmpty()) {
            resolve2(modules, results, results.size());
        }
    }

    private void checkCycleDependencies(Collection<Module> modules) {
        Stack<Module> s = new Stack<Module>();
        s.addAll(modules);
        String message = "You have a cyclic dependency : " + printGraph(s, modules.iterator().next());
        throw new BuildException(message);
    }

    private void removeDependency(Collection<Module> depModules, Collection<Module> results) {
        Collection<Module> toRemove = new ArrayList<Module>();
        for (Module m : depModules) {
            if (results.contains(m)) {
                toRemove.add(m);
            }
        }
        for (Module m : toRemove) {
            depModules.remove(m);
        }
    }
    
    public Collection<Module> resolve(Collection<Module> modules) {
        Collection<Module> results = new ArrayList<Module>();
        Stack<Module> stack1 = new Stack<Module>();
        Stack<Module> stack2 = new Stack<Module>();

        stack1.addAll(modules);

        while (true) {
            //System.out.println(stack1 + " -- " + stack2 + " -- " + results);
            if (stack1.empty() && !stack2.empty()) {
                while (!stack2.empty()) {
                    Module m4 = stack2.pop();
                    if (!results.contains(m4)) {
                        results.add(m4);
                    }
                }
            }

            if (stack1.empty() && stack2.empty()) {
                break;
            }

            Module m = stack1.pop();
            stack2.push(m);

            Module m2 = stack2.pop();

            Collection<Module> subM = m2.getDependencies();

            if ((subM.isEmpty() || results.containsAll(subM)) && !results.contains(m2)) {
                results.add(m2);
                continue;
            } else {
                if (stack2.contains(m2) && stack2.indexOf(m2) == 0) {
                    String message = "You have a cyclic dependency : " + printGraph(stack2, m2);
                    throw new BuildException(message);
                }
                stack2.push(m2);
            }

            for (Module m3 : subM) {
                if (!stack1.contains(m3)) {
                    stack1.push(m3);
                }
            }

        }
        return results;
    }

    public String printGraph(Stack<Module> modules, Module m) {
        StringBuffer sb = new StringBuffer();
        sb.append(m.getName());
        while (!modules.empty()) {
            sb.append(" <-- ");
            sb.append(modules.pop());
        }

        return sb.toString();
    }
}